λ¬Έμ
Programmers - μμ κ²μ
π Logic
// -λ₯Ό λΆμ΄λ©΄μ κ°λ₯ν μ‘°ν©μ μμ±νμ¬ mapμ μΆκ°νλ€.
private static void makeComb(int length) {
if (length == 4) {
String key = String.join("", combStr);
scoreMap.putIfAbsent(key, new ArrayList<>());
scoreMap.get(key).add(infoScore);
} else {
// -κ° μλ κ²½μ°μ -μΈ κ²½μ°λ‘ λλ κ°λ₯ν μ‘°ν© μμ±
combStr[length] = infoLine[length];
makeComb(length + 1);
combStr[length] = "-";
makeComb(length + 1);
}
}
- -λ₯Ό λΆμ΄λ©΄μ κ°λ₯ν μ 보λ₯Ό λ§λλ ν¨μ
- DFS λ°©μμΌλ‘ κΈ°μ‘΄μ μ 보λ₯Ό μ¬μ©νκ±°λ, -λ₯Ό λΆμ΄κ±°λ νμ¬ μμ±νλ€.
π CODE
μ½λ 보기/μ κΈ°π«
import java.util.*;
class Solution {
// μΈμ΄, μ§κ΅°, κ²½λ ₯, μμΈνΈλλ₯Ό keyλ‘ κ°μ§κ³ , μ μ 리μ€νΈλ₯Ό κ°μΌλ‘ κ°μ§λ map μ μΈ
static Map<String, ArrayList<Integer>> scoreMap = new HashMap<>();
// μ‘°ν© μμ±μ μν΄ μ¬μ©ν λ°°μ΄, μ½ν
μ μ, μ§μμμ μ 보 λ°°μ΄
static String[] combStr;
static int infoScore;
static String[] infoLine;
public int[] solution(String[] info, String[] query) {
int[] answer = new int[query.length];
// μ£Όμ΄μ§ info λ°°μ΄μ κ°μ§κ³ scoreMap μ΄κΈ°ν
// -λ₯Ό ν¬ν¨ν λͺ¨λ μ‘°ν©μ μμ±νμ¬ mapμ keyλ‘ μΆκ°
initScoreMap(info);
// μ΄μ§νμμ μν΄ μ μ 리μ€νΈλ₯Ό μ€λ¦μ°¨μμΌλ‘ μ λ ¬
for (String key : scoreMap.keySet())
Collections.sort(scoreMap.get(key));
for (int i = 0; i < query.length; i++) {
String[] line = query[i].split(" and | ");
StringBuilder sb = new StringBuilder(line[0] + line[1] + line[2] + line[3]);
String key = sb.toString();
int score = Integer.parseInt(line[4]);
if (scoreMap.containsKey(key)) {
ArrayList<Integer> list = scoreMap.get(key);
answer[i] = list.size() - findLower(list, score);
}
}
return answer;
}
private static void initScoreMap(String[] info) {
for (String i : info) {
combStr = new String[4];
infoLine = i.split(" ");
infoScore = Integer.parseInt(infoLine[4]);
makeComb(0);
}
}
// -λ₯Ό λΆμ΄λ©΄μ κ°λ₯ν μ‘°ν©μ μμ±νμ¬ mapμ μΆκ°νλ€.
private static void makeComb(int length) {
if (length == 4) {
String key = String.join("", combStr);
scoreMap.putIfAbsent(key, new ArrayList<>());
scoreMap.get(key).add(infoScore);
} else {
// -κ° μλ κ²½μ°μ -μΈ κ²½μ°λ‘ λλ κ°λ₯ν μ‘°ν© μμ±
combStr[length] = infoLine[length];
makeComb(length + 1);
combStr[length] = "-";
makeComb(length + 1);
}
}
private static int findLower(ArrayList<Integer> list, int value) {
int left = 0;
int right = list.size() - 1;
while (left <= right) {
int mid = (left + right) / 2;
int v = list.get(mid);
if (v < value) left = mid + 1;
else right = mid - 1;
}
return left;
}
}
βοΈ Review
- -κ° ν¬ν¨λ κ²½μ°λ₯Ό μν΄ κ°λ₯ν λͺ¨λ μ 보λ₯Ό λ§λ€μ΄λκ³ μ΄λ₯Ό μ¬μ©νλ μμ΄λμ΄λ₯Ό μ¬μ©νλ€.
- μ΄μ§ νμμ μ¬μ©ν΄ λΉ λ₯΄κ² μΈμμ ꡬνλ μμ΄λμ΄κ° μ£Όμνλ κ² κ°λ€.